package Hot100.Medium.GreedyAndDP.DynamicPlanning.CompleteBag;

import java.util.HashSet;
import java.util.List;

public class LC139_WordSplit {
    public static void main(String[] args) {

    }
    public boolean wordBreak(String s, List<String> wordDict){
        HashSet<String> set = new HashSet<>(wordDict);
        // 依旧是完全背包，字符串s表示背包，字典中的单词表示物品
        // 确定dp数组含义 dp[i]表示字符串长度为i，dp[i]为true时表示可以拆分为字典中出现的单词
        boolean[] dp = new boolean[s.length() + 1];
        // dp数组初始化。
        dp[0] = true;

        // 确定递推公式，如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）
        // 所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
        // 对于遍历顺序，本题是求排列数，因为单词可以按任意顺序排列，因此for外层是背包，内层是物品，与组合数相反
        for(int i = 1; i <= s.length(); i++){
            for(int j = 0; j < i && !dp[i]; j++){
                if(set.contains(s.substring(j,i)) && dp[j]){
                    dp[i] = true;
                }
            }
        }
        return dp[s.length()];
    }
}
